package my.jwds.p653;

import my.jwds.p94.TreeNode;

import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

public class FindTarget {

    public static void main(String[] args) {

        FindTarget obj = new FindTarget();
        long start = System.currentTimeMillis();
        System.out.println(obj.findTarget(TreeNode.to_binaryHaveNull(new Integer[]{5,3,6,2,4,null,7}),9));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    public boolean findTarget(TreeNode root, int k) {
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        Set<Integer> set = new HashSet<>();
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            System.out.println(node.val);
            if (node.val == k || set.contains(node.val))return true;
            set.add(k-node.val);
            if (node.right != null){
                stack.push(node.right);
            }

            if (node.left != null){
                stack.push(node.left);
            }
        }
        return false;
    }
}